#pragma once
#include<iostream>
#include<vector>
#include<unordered_map>
namespace bit
{
	
	template<class V>
	class HashTableNode
	{
	public:
		typedef typename HashTableNode<V> Node;
		HashTableNode(const V& value):
			date(value),
			next(nullptr)
		{
		}
	public:
		Node* next;
		V date;
	};
	template<class V,class REF,class PTR,class KOFT, class DeafultHashFunc >
	class HashTableIterator
	{
	public:
		typedef typename HashTableNode<V> Node;
		typedef typename HashTableIterator<V,REF,PTR, KOFT, DeafultHashFunc> Self;
		typedef typename HashTableIterator<V,  V&,  V*, KOFT, DeafultHashFunc> iterator;
		typedef typename HashTableIterator<V, const V&, const V*, KOFT, DeafultHashFunc> const_iterator;
		HashTableIterator(const iterator& value):
			node(value.node),
			_table(value._table)
		{}
		HashTableIterator( Node*value, std::vector<Node*>* table):
			node(value),
			_table(table)
		{}
		HashTableIterator(Node* value, const std::vector<Node*>* table) :
			node(value),
			_table(table)
		{}
		Self operator++()
		{
			if (node)
			{
				if (node->next)
				{
					node = node->next;
				}
				else
				{
					KOFT kot;
					DeafultHashFunc func;
					size_t hashi = func(kot(node->date)) % _table->size();
					hashi++;
					
					while (hashi < _table->size())
					{

						if ((*_table)[hashi])
						{
							node = (*_table)[hashi];
							break;
								
						}
						else
						{
							hashi++;
							continue;

						}

					}
					if (hashi >= _table->size())
					{
						node = nullptr;
					}
				}
			}
			return *this;

		}

		bool operator!=(const iterator& other)
		{
			return node != other.node;
		}

		bool operator!=(const const_iterator& other)const
		{
			return node != other.node;
		}

		

		const_iterator begin()const
		{
			Node* cur = _table[0];
			int pos = 0;
			while (pos < _table.size())
			{
				if (cur)
				{
					return const_iterator(cur, &_table);
				}
				else
				{
					pos++;
					cur = _table[pos];
				}
			}

		}

	

		 const_iterator end()const
		{
			return const_iterator(nullptr, &_table);
		}

		REF operator*()
		{
			//KOFT t;
			return node->date;
		}
		PTR operator->()
		{
			//KOFT t;
			return &node->date;
		}

	public:
		Node* node;
		const std::vector<Node*>* _table;


	};
	template<class V>
	class HashFunc
	{
	public:
		size_t operator()(const V& value)
		{
			return (size_t)value;
		}
	};
	template<>
	class HashFunc<int>
	{
	public:
		size_t operator()(const int& value)
		{
			return (size_t)value;
		}
	};
	template<>
	class HashFunc< std::string>
	{
	public:
		size_t operator()(const std::string& str )
		{
			size_t hash = 0;
			for (auto ch : str)
			{
				hash *= 131;
				hash += ch;
			}

			return hash;
		}
	};
	template<class K,class V,class KOFT,class DeafultHashFunc=HashFunc<K>>
	class HashTable
	{
	public:
		typedef typename HashTableNode<V> Node;
		typedef typename HashTableIterator<V, V&, V*, KOFT, DeafultHashFunc> iterator;
		typedef typename HashTableIterator<V, const V&, const V*, KOFT, DeafultHashFunc> const_iterator;
		HashTable()
		{
			_table.resize(10,nullptr);
		}
		std::pair<iterator,bool> insert(const V& value)
		{
			KOFT kot;
			DeafultHashFunc func;
			//size_t hashi = fun(kot(value));
			if (real_size >= _table.size())
			{
				EXpansion();
			}
			size_t hashi = func(kot(value)) % _table.size();
			Node* cur = new Node(value);
			if (_table[hashi])
			{
				Node* temp = _table[hashi];
				if (cur->date == temp->date)
				{
					return std::pair<iterator, bool>(iterator(temp, &_table), true);
				}
				while(temp->next)
				{
					temp = temp->next;
				}
				cur->next = temp->next;
				temp->next = cur;
				

			}
			else
			{
			
				cur->next = _table[hashi];
				_table[hashi] = cur;
			}
			real_size++;
			return std::pair<iterator,bool>(iterator(cur,&_table),true);

		}

		const_iterator find(const K& key )const
		{
			KOFT kot;
			DeafultHashFunc func;
			size_t hashi = func(key) % _table.size();
			Node* cur = _table[hashi];
			while (cur)
			{
				if (key == kot(cur->date))
				{
					break;
				}
				else
				{
					cur = cur->next;
				}
			}
			return const_iterator(cur,&_table);
		}

		bool delet(const K& key)
		{
			DeafultHashFunc func;
			size_t hashi = func(key) % _table.size();
			Node* preve = nullptr;
			Node* cur = _table[hashi];
			while (cur)
			{
				if (key == cur->date)
				{
					if (preve == nullptr)
					{
						_table[hashi] = nullptr;
					}
					else
					{
						preve->next = cur->next;
					}
					real_size--;
					delete(cur);
					
				}
				else
				{
					preve = cur;
					cur = cur->next;
				}
			}


		}

		void EXpansion()
		{
		
			
			std::vector<Node*> other;
			other.resize(_table.size() * 2);
			Node* cur=_table[0];
			Node* next = cur->next;
			size_t i = 0;
			size_t hashi = 0;
			KOFT kot;
			DeafultHashFunc func;
			while(cur)
			{
				hashi = func(kot(cur->date)) % other.size();
				if (other[hashi])
				{
					Node* temp = other[hashi];
					while (temp->next)
					{
						temp = temp->next;
					}
					cur->next = temp->next;
					temp->next = cur;


				}
				else
				{

					cur->next = other[hashi];
					other[hashi] = cur;
				}
				cur = next;
				while (cur==nullptr )
				{
					i++;
					if (i < _table.size())
					{
						cur = _table[i];
					}
					else
					{
						_table.swap(other);
						return;
					}

				}
				next = cur->next;
			}	
			
		}
		iterator  begin()
		{
			Node* cur = _table[0];
			int pos = 0;
			while (pos < _table.size())
			{
				if (cur)
				{
					return iterator(cur, &_table);
				}
				else
				{
					pos++;
					cur = _table[pos];
				}
			}
		}
		const_iterator begin()const
		{
			Node* cur = _table[0];
			int pos = 0;
			while (pos < _table.size())
			{
				if (cur)
				{
					return iterator(cur, &_table);
				}
				else
				{
					pos++;
					cur = _table[pos];
				}
			}
		}
		

		iterator end()
		{
			return iterator(nullptr, &_table);
		}

		const_iterator end()const
		{
			return  iterator(nullptr, &_table);
		}
	
	

		
		
	public:
		std::vector<Node*> _table;
		size_t real_size = 0;

	};

}

